/**概念：
 * 希尔排序是插入排序的一种又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本。
 * 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，
 * 每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。
 * 
 * 思想：
 * 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。
 * 所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2，以此类推。
 * 
 *   时间复杂度：最好O(n),最坏O(n*n)
   空间：O(1)
   不稳定排序（由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。）
 * 
 * 捷径：改造插入排序算法，获得希尔排序算法
引入gap，初始值为1；将原来插入排序中的所有1用gap替换
给原来插入排序和循环外面加一层循环（希尔排序的精髓所在）
将gap的初始值从1修改成数组长度的一半，直接从插入排序变成希尔排序

 * @param {*} arr 
 * @returns 
 */
function hillSort(arr) {
  if (!Array.isArray(arr)) throw new TypeError("argument must be a array");
  const _newArr = arr;
  const len = _newArr.length;
  if (len < 2) return _newArr;

  // 增量值，默认取数组一半，len>>1相当于向下取整
  let gap = len >> 1;

  while (gap > 0) {
    for (let i = gap; i < len; i++) {
      const current = _newArr[i];

      // j -gap，目的是要取当前和i同一组的
      let j = i - gap;

      while (j >= 0 && _newArr[j] > current) {
        // 对每个同组的进行直接插入排序
        _newArr[j + gap] = _newArr[j];
        j -= gap;
      }

      _newArr[j + gap] = current;
    }

    // 下一次继续取一半
    gap = gap >> 2;
  }

  return _newArr;
}

// egg:

const arr = [1, 3, 5, 4, 6, 8, 2, 7];
console.log("[ arr ] >", hillSort(arr));
